Information Transmission under Random Emission Constraints
Identifieur interne : 000D58 ( Main/Exploration ); précédent : 000D57; suivant : 000D59Information Transmission under Random Emission Constraints
Auteurs : Francis Comets [France] ; François Delarue [France] ; René Schott [France]Source :
- Combinatorics, Probability and Computing [ 0963-5483 ] ; 2014.
English descriptors
- mix :
Abstract
We model the transmission of a message on the complete graph with n vertices and limited resources. The vertices of the graph represent servers that may broadcast the message at random. Each server has a random emission capital that decreases at each emission. Quantities of interest are the number of servers that receive the information before the capital of all the informed servers is exhausted and the exhaustion time. We establish limit theorems (law of large numbers, central limit theorem and large deviation principle), as n tends to infinity, for the proportion of visited vertices before exhaustion and for the total duration. The analysis relies on a construction of the transmission procedure as a dynamical selection of successful nodes in a Galton-Watson tree with respect to the success epochs of the coupon collector problem.
Url:
Affiliations:
- France
- Grand Est, Lorraine (région), Provence-Alpes-Côte d'Azur
- Metz, Nancy, Nice
- Université Nice Sophia Antipolis, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 002B20
- to stream Hal, to step Curation: 002B20
- to stream Hal, to step Checkpoint: 000D28
- to stream Main, to step Merge: 000E69
- to stream Main, to step Curation: 000D58
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Information Transmission under Random Emission Constraints</title><author><name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-102" status="VALID"><idno type="RNSR">199712645M</idno><orgName>Laboratoire de Probabilités et Modèles Aléatoires</orgName><orgName type="acronym">LPMA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.proba.jussieu.fr/</ref></desc><listRelation><relation active="#struct-93591" type="direct"></relation><relation active="#struct-300301" type="direct"></relation><relation name="UMR7599" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID"><orgName>Université Pierre et Marie Curie - Paris 6</orgName><orgName type="acronym">UPMC</orgName><desc><address><addrLine>4 place Jussieu - 75005 Paris</addrLine><country key="FR"></country></address><ref type="url">http://www.upmc.fr/</ref></desc></org></tutelle><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID"><orgName>Université Paris Diderot - Paris 7</orgName><orgName type="acronym">UP7</orgName><desc><address><addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-paris-diderot.fr</ref></desc></org></tutelle><tutelle name="UMR7599" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-26" status="OLD"><orgName>Laboratoire Jean Alexandre Dieudonné</orgName><orgName type="acronym">JAD</orgName><desc><address><addrLine>Université de Nice - Sophia Antipolis U.M.R. no 6621 du C.N.R.S. Parc Valrose 06108 Nice Cedex 02 France</addrLine><country key="FR"></country></address><ref type="url">http://math.unice.fr/</ref></desc><listRelation><relation name="UMR6621" active="#struct-441569" type="direct"></relation><relation active="#struct-117617" type="direct"></relation></listRelation><tutelles><tutelle name="UMR6621" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-117617" type="direct"><org type="institution" xml:id="struct-117617" status="VALID"><orgName>Université Nice Sophia Antipolis</orgName><orgName type="acronym">UNS</orgName><desc><address><addrLine>Parc Valrose - BP 2135 - 06103 Nice cedex 2</addrLine><country key="FR"></country></address><ref type="url">http://unice.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nice</settlement><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region></placeName><orgName type="university">Université Nice Sophia Antipolis</orgName></affiliation></author><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388679" status="VALID"><orgName>Probabilités et statistiques</orgName><desc><address><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/equipesIECL_probstat.html</ref></desc><listRelation><relation active="#struct-211251" type="direct"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7502" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-211251" type="direct"><org type="laboratory" xml:id="struct-211251" status="VALID"><idno type="IdRef">180064606</idno><idno type="RNSR">199712570F</idno><idno type="IdUnivLorraine">[UL]RSB--</idno><orgName>Institut Élie Cartan de Lorraine</orgName><orgName type="acronym">IECL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Université de Lorraine, Boulevard des Aiguillettes BP 70239 54506 Vandoeuvre-les-Nancy CedexIle du Saulcy - 57 045 Metz Cedex 01</addrLine><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/</ref></desc><listRelation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7502" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7502" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00637304</idno><idno type="halId">hal-00637304</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00637304</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-00637304</idno><date when="2014">2014</date><idno type="wicri:Area/Hal/Corpus">002B20</idno><idno type="wicri:Area/Hal/Curation">002B20</idno><idno type="wicri:Area/Hal/Checkpoint">000D28</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000D28</idno><idno type="wicri:doubleKey">0963-5483:2014:Comets F:information:transmission:under</idno><idno type="wicri:Area/Main/Merge">000E69</idno><idno type="wicri:Area/Main/Curation">000D58</idno><idno type="wicri:Area/Main/Exploration">000D58</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Information Transmission under Random Emission Constraints</title><author><name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-102" status="VALID"><idno type="RNSR">199712645M</idno><orgName>Laboratoire de Probabilités et Modèles Aléatoires</orgName><orgName type="acronym">LPMA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.proba.jussieu.fr/</ref></desc><listRelation><relation active="#struct-93591" type="direct"></relation><relation active="#struct-300301" type="direct"></relation><relation name="UMR7599" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID"><orgName>Université Pierre et Marie Curie - Paris 6</orgName><orgName type="acronym">UPMC</orgName><desc><address><addrLine>4 place Jussieu - 75005 Paris</addrLine><country key="FR"></country></address><ref type="url">http://www.upmc.fr/</ref></desc></org></tutelle><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID"><orgName>Université Paris Diderot - Paris 7</orgName><orgName type="acronym">UP7</orgName><desc><address><addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-paris-diderot.fr</ref></desc></org></tutelle><tutelle name="UMR7599" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-26" status="OLD"><orgName>Laboratoire Jean Alexandre Dieudonné</orgName><orgName type="acronym">JAD</orgName><desc><address><addrLine>Université de Nice - Sophia Antipolis U.M.R. no 6621 du C.N.R.S. Parc Valrose 06108 Nice Cedex 02 France</addrLine><country key="FR"></country></address><ref type="url">http://math.unice.fr/</ref></desc><listRelation><relation name="UMR6621" active="#struct-441569" type="direct"></relation><relation active="#struct-117617" type="direct"></relation></listRelation><tutelles><tutelle name="UMR6621" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-117617" type="direct"><org type="institution" xml:id="struct-117617" status="VALID"><orgName>Université Nice Sophia Antipolis</orgName><orgName type="acronym">UNS</orgName><desc><address><addrLine>Parc Valrose - BP 2135 - 06103 Nice cedex 2</addrLine><country key="FR"></country></address><ref type="url">http://unice.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nice</settlement><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region></placeName><orgName type="university">Université Nice Sophia Antipolis</orgName></affiliation></author><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388679" status="VALID"><orgName>Probabilités et statistiques</orgName><desc><address><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/equipesIECL_probstat.html</ref></desc><listRelation><relation active="#struct-211251" type="direct"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7502" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-211251" type="direct"><org type="laboratory" xml:id="struct-211251" status="VALID"><idno type="IdRef">180064606</idno><idno type="RNSR">199712570F</idno><idno type="IdUnivLorraine">[UL]RSB--</idno><orgName>Institut Élie Cartan de Lorraine</orgName><orgName type="acronym">IECL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Université de Lorraine, Boulevard des Aiguillettes BP 70239 54506 Vandoeuvre-les-Nancy CedexIle du Saulcy - 57 045 Metz Cedex 01</addrLine><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/</ref></desc><listRelation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7502" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7502" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></analytic><series><title level="j">Combinatorics, Probability and Computing</title><idno type="ISSN">0963-5483</idno><imprint><date type="datePub">2014</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Galton-Watson tree</term><term>complete graph</term><term>coupon collector problem</term><term>epidemic model</term><term>information transmission</term><term>large deviations</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We model the transmission of a message on the complete graph with n vertices and limited resources. The vertices of the graph represent servers that may broadcast the message at random. Each server has a random emission capital that decreases at each emission. Quantities of interest are the number of servers that receive the information before the capital of all the informed servers is exhausted and the exhaustion time. We establish limit theorems (law of large numbers, central limit theorem and large deviation principle), as n tends to infinity, for the proportion of visited vertices before exhaustion and for the total duration. The analysis relies on a construction of the transmission procedure as a dynamical selection of successful nodes in a Galton-Watson tree with respect to the success epochs of the coupon collector problem.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Provence-Alpes-Côte d'Azur</li></region><settlement><li>Metz</li><li>Nancy</li><li>Nice</li></settlement><orgName><li>Université Nice Sophia Antipolis</li><li>Université de Lorraine</li></orgName></list><tree><country name="France"><noRegion><name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name></noRegion><name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000D58 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000D58 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-00637304
|texte= Information Transmission under Random Emission Constraints
}}
| This area was generated with Dilib version V0.6.33. |  |